package com.zlk.algorithm.algorithm.sort;

/**
 * @program: algorithm
 * @ClassName Trail
 * @description: 前缀树实现
 * 像 Google、百度这样的搜索引擎，它们的关键词提示功能非常全面和精准，肯定做了很多优化，但万变不离其宗，
 *    底层最基本的原理就是这种数据结构：Trie 树。
 * Trie 树，也叫“字典树”。顾名思义，它是一个树形结构。它是一种专门处理字符串匹配的数据结构，用来解决
 *    在一组字符串集合中快速查找某个字符串的问题。
 * 相对于hash  它可以查看指定路径经过的次数，以及字符出现的次数
 * @author: slfang
 * @create: 2024-01-26 15:31
 * @Version 1.0
 **/
public class Trie {

    /**
     * @description:
     *
     *   在一组字符串中查找字符串，Trie 树实际上表现得并不好。它对要处理的字符串有极其严苛的要求。
     *       第一，字符串中包含的字符集不能太大。如果字符集太大，那存储空间可能就会浪费很多。即便可以优化，
     *       但也要付出牺牲查询、插入效率的代价。
     *   第二，要求字符串的前缀重合比较多，不然空间消耗会变大很多。
     *
     *   Trie 树只是不适合精确匹配查找，这种问题更适合用散列表或者红黑树来解决。
     *   Trie 树比较适合的是查找前缀匹配的字符串，也就是类似开篇问题的那种场景
     *   Trie 树的这个应用可以扩展到更加广泛的一个应用上，就是自动输入补全，比如输入法自动补全功能、
     *       IDE 代码编辑器自动补全功能、浏览器网址输入的自动补全功能等等。
     **/

    private TrieNode root = new TrieNode();
    /**
     * Trie 树是一个多叉树、二叉树中，一个节点的左右子节点是通过两个指针来存储的
     */
    class TrieNode{
        public int pass;
        public int end;
        /**
         * 下节点 假设字符26个字符  数组的索引 0-25 分别表示 a 字符到 z字符
         */
        public TrieNode[] nexts;
        public TrieNode() {
            pass = 0;
            end = 0;
            //消耗空间，可以解决，将26长度的数组 比如有序数组、跳表、散列表、红黑树等。
            nexts = new TrieNode[26];
        }
    }

    public void add(String str){
        if("".equals(str)||str==null){
            return ;
        }
        TrieNode node = root;
        node.pass++;
        char[] chars = str.toCharArray();
        for (char aChar : chars) {
            int index = aChar-'a';
            TrieNode trieNode = null;
            if(node.nexts[index] == null){
                trieNode = new TrieNode();
            }
            trieNode.pass++;
            node.nexts[index] = trieNode;
            node = trieNode;
        }
        node.end++;
    }

    public void erase(String word) {
        if (countWordsEqualTo(word) != 0) {
            char[] chs = word.toCharArray();
            TrieNode node = root;
            node.pass--;
            int path = 0;
            for (int i = 0; i < chs.length; i++) {
                path = chs[i] - 'a';

                //此处防止内存泄露
                if (--node.nexts[path].pass == 0) {
                    node.nexts[path] = null;
                    return;
                }
                node = node.nexts[path];
            }
            node.end--;
        }
    }


    /**
     * 查找多少个word的字符
     * @return
     */
    int countWordsEqualTo(String word){
        if("".equals(word)||word==null){
            return 0;
        }
        char[] chars = word.toCharArray();
        TrieNode node = root;
        for (char aChar : chars) {
            int index = aChar-'a';
            if(node.nexts[index]==null){
                return 0;
            }
            node = node.nexts[index];
        }
        return node.end;
    }


    /**
     * 查找存在多少个以pre作为前缀的字符
     * @param pre
     * @return
     */
    public int countWordsStartingWith(String pre) {
        if("".equals(pre)||pre==null){
            return 0;
        }
        char[] chars = pre.toCharArray();
        TrieNode node = root;
        for (char aChar : chars) {
            int index = aChar-'a';
            if(node.nexts[index]==null){
                return 0;
            }
            node = node.nexts[index];
        }
        return node.pass;
    }

}
